/*   Written by Zhang Jun
     2000.4.28
*/
#include "stdio.h"
#include "alloc.h"

#define NODE struct Node

struct Node{
	float coef;
	int   expn;
	struct Node *link;
	};

typedef NODE *Polynomial;

NODE *MakeNode(float coef,int expn)
{
 NODE *p;
 p=(NODE *)malloc(sizeof(NODE));
 p->coef=coef;
 p->expn=expn;
 p->link=NULL;
 return p;
}

/*Create a new Polynomail */
void CreatePoly(Polynomial *p,int m)
{
 float tempcoef;
 int tempexpn;
 int i;
 NODE *q1,*q2;

 *p=MakeNode(0,-1);

 q2=*p;
 for(i=1;i<=m;i++)                   /*Input coef and expn increasingly */
 {
  cprintf("No.%d(Total %d)Input Coef:",i,m);
  cscanf("%f",&tempcoef);
  cprintf("No.%d(Total %d)Input Expn:",i,m);
  cscanf("%d",&tempexpn);

  q1=q2->link;
  q2->link=MakeNode(tempcoef,tempexpn);
  q2->link->link=q1;
 }
}

void DestoryPoly(Polynomial *p)
{
 NODE *q1,*q2;

 q1=q2=*p;
 while(q1)
 {
  q2=q2->link;
  free(q1);
  q1=q2;
 }
 *p=NULL;
}

/*Copy the list from pointer p to the tail */
NODE *CopyPart(NODE *pn)
{
 NODE *ret,*hp,*p;

 if(!pn)
 return NULL;

 ret=hp=p=MakeNode(pn->coef,pn->expn);
 pn=pn->link;
 while(pn)
 {
  p=MakeNode(pn->coef,pn->expn);
  hp->link=p;
  hp=p;
  pn=pn->link;
 }
 return ret;
}

/* Copy a polynomial */
Polynomial CopyPoly(Polynomial p)
{
 return CopyPart(p);
}

/*Print a polynomial */
void Display(Polynomial p)
{
 NODE *q;
 q=p->link;

 if(!q)
 {
  cprintf("0");
  return;
 }

 while(q)
 {
  if(q->link==NULL)
  {
	if(!(q->expn))
	cprintf("<%f>",q->coef);
	else
	cprintf("<%f>X(%d)",q->coef,q->expn);
  }
  else
	cprintf("<%f>X(%d)+",q->coef,q->expn);
  q=q->link;
 }
}

/*Compare the expns */
char CompareExpn(int a,int b)
{
 if(a>b) return  '>';
 else
 {
  if(a<b) return '<';
  else    return '=';
 }
}

/* Link polynomials: pa=pa+pb and clear pb*/
void LinkPoly(Polynomial pa,Polynomial pb)
{
 NODE *ha,*hb,*qa,*qb;

 ha=pa;
 hb=pb;
 qa=ha->link;
 qb=hb->link;

 while(qa&&qb)
 {
  switch(CompareExpn(qa->expn,qb->expn))
  {
  case '>':
   ha=ha->link;
   qa=qa->link;
   break;
  case '<' :
    hb->link=qb->link;
    ha->link=qb;
    qb->link=qa;
    qb=hb->link;
    ha=ha->link;
    break;
   case '=':
    if((qa->coef+qb->coef)==0)
    {
     ha->link=qa->link;
     free(qa);
     qa=ha->link;

     hb->link=qb->link;
     free(qb);
     qb=hb->link;
    }
    else
    {
     qa->coef+=qb->coef;
     qa=qa->link;
     ha=ha->link;

     hb->link=qb->link;
     free(qb);
     qb=hb->link;
    }
   break;
  }
 }
 if(qb)
 {
  ha->link=qb;
  hb->link=NULL;
 }
}

/* Add Polynomials ret=pa+pb,pa and pb still exist*/
Polynomial AddPoly(Polynomial pa,Polynomial pb)
{
 NODE *qa,*qb,*qc,*hc;
 Polynomial pc;

 CreatePoly(&pc,0); /*Create a new Polynomial */
 hc=pc;
 qa=pa->link;
 qb=pb->link;
 while(qa&&qb)
 {
  switch(CompareExpn(qa->expn,qb->expn))
  {
  case '>':
    qc=MakeNode(qa->coef,qa->expn);
    hc->link=qc;
    hc=qc;
    qa=qa->link;
    break;
  case '<' :
    qc=MakeNode(qb->coef,qb->expn);
    hc->link=qc;
    hc=qc;
    qb=qb->link;
    break;
  case '=':
    if((qa->coef+qb->coef)==0)
    {
     qa=qa->link;
     qb=qb->link;
    }
    else
    {
     qc=MakeNode((qa->coef+qb->coef),qa->expn);
     hc->link=qc;
     hc=qc;

     qa=qa->link;
     qb=qb->link;
    }
   break;
  }
 }
 if(qa)
 hc->link=CopyPart(qa);
 if(qb)
 hc->link=CopyPart(qb);

 return pc;
}

void NotPart(NODE *p)
{
 while(p)
 {
  p->coef=-(p->coef);
  p=p->link;
 }
}

void NotPoly(Polynomial p)
{
 p=p->link;
 NotPart(p);
}

/* Sub Polynomials ret=pa-pb,pa and pb still exist*/
Polynomial SubPoly(Polynomial pa,Polynomial pb)
{
 Polynomial pc,temppb;

 temppb=CopyPoly(pb);
 NotPoly(temppb);
 pc=AddPoly(pa,temppb);
 DestoryPoly(&temppb);
 return pc;
}

void MultiTerm(Polynomial p,NODE *pn)
{
 if(!pn)
 return;

 for(p=p->link;p;p=p->link)
 {
  p->coef*=pn->coef;
  p->expn+=pn->expn;
 }
}

/*Multiply polynomials ret=pa*pb pa,pb still exist*/
Polynomial MultiPoly(Polynomial pa,Polynomial pb)
{
 NODE *qb;
 Polynomial pc,temppa;

 if(pa->link==0||pb->link==0)
 {
  CreatePoly(&pc,0);
  return pc;
 }

 pc=CopyPoly(pa);
 qb=pb->link;
 MultiTerm(pc,qb);

 for(qb=qb->link;qb;qb=qb->link)
 {
  temppa=CopyPoly(pa);
  MultiTerm(temppa,qb);
  LinkPoly(pc,temppa);
  DestoryPoly(&temppa);
 }
 return pc;
}

NODE *DivideSingleNode(NODE *pna,NODE *pnb)
{
 if(pna==NULL||pnb==NULL||pna->expn<pnb->expn)
 return NULL;

 return MakeNode((pna->coef/pnb->coef),(pna->expn-pnb->expn));
}

/*Divide Polynomials ret=pa/pb,rest return YU SHU
pa,pb still exist*/
Polynomial DividePoly(Polynomial pa,Polynomial pb,Polynomial *rest)
{
 NODE *pt,*hc;
 NODE *tempn;
 Polynomial pc,pr,temp;

 CreatePoly(&pc,0);
 if(pb->link==0)                        /* pb is empty*/
 {
   CreatePoly(rest,0);
   return pc;
 }

 pr=CopyPoly(pa);
 hc=pc;

 pt=DivideSingleNode(pr->link,pb->link);
 while(pt)
 {
   temp=CopyPoly(pb);
   MultiTerm(temp,pt);

   tempn=pr;
   pr=SubPoly(pr,temp);

   DestoryPoly(&temp);
   DestoryPoly(&tempn);

   hc->link=pt;
   hc=pt;
   pt=DivideSingleNode(pr->link,pb->link);
 }
 (*rest)=pr;
 return pc;
}
